﻿//923. 三数之和的多种可能
//给定一个整数数组 arr ，以及一个整数 target 作为目标值，返回满足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 的元组 i, j, k 的数量。
//由于结果会非常大，请返回 109 + 7 的模。


class Solution {
public:
    int e = 1000000007;
    int threeSumMulti(vector<int>& nums, int target)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < n - 2; i++)
        {
            int x = nums[i];
            int left = i + 1, right = n - 1;
            while (left < right)
            {
                int sum = x + nums[left] + nums[right];
                if (sum > target)
                {
                    right--;
                }
                else if (sum < target)
                {
                    left++;
                }
                else
                {
                    if (nums[left] == nums[right])
                    {
                        ans = (ans + (right - left + 1) * (right - left) / 2 + 0L) % e;
                        break;
                    }
                    else
                    {
                        int cnt1 = 0, cnt2 = 0;
                        int l = nums[left], r = nums[right];
                        while (l == nums[left])
                        {
                            left++;
                            cnt1++;
                        }
                        while (r == nums[right])
                        {
                            right--;
                            cnt2++;
                        }
                        ans += (1L * cnt1 * cnt2) % e;
                    }
                }
            }
        }
        return ans;
    }
};